package test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-08-16 20:14
 */
public class LRU_LinkedList {

}


class LRUCache {
    Map<Integer, ListNode> map = new HashMap<>();
    LinkedList<ListNode> list = new LinkedList<>();
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        ListNode node = map.get(key);
        remove(node);
        addFirst(node);
        return node.val;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            ListNode node = map.get(key);
            node.val = value;
            // map.put(key,node);
            remove(node);
            addFirst(node);
        }else{
            ListNode node = new ListNode(key,value);
            addFirst(node);
            map.put(key,node);
            //
            if(map.size()>this.capacity){
                // 移除最后一个结点
                ListNode del = list.get(list.size() - 1);
                // 从map移除
                map.remove(del.key);
                // 从链表中移除
                remove(del);
            }
        }
    }

    // 从链表中删除某个结点
    void remove(ListNode del){
        // 从链表中移除
        list.remove(del);
    }

    // 在链表头部添加结点
    void addFirst(ListNode node){
        list.addFirst(node);
    }
}

// 结点类型
class ListNode{
    int key;
    int val;
    ListNode(){}
    ListNode(int key,int val){
        this.key = key;
        this.val = val;
    }
}
